package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
完全背包问题：
物品种类有限，但每种物品数量无限
背包有最大承重

首先在初始化最后一行的时候有所不同：
	初始化时，当只考虑一件物品a时，state[row][j] = values[row]*j/weight[row]
然后在递推的时候有些不同：
	state[row][j] = max{state[row+1][j],state[row][j-weight[row]]+values[row]}，
	即不抓时用现在的容量去匹配下面行
	要抓的时候，先抓到这个物品的价值，然后用剩下的容量去匹配同一行，
为什么匹配同一行?这是因为剩下的容量可以重复抓当前物品（不限数量）
同时必须理解，抓一个之后用剩余的容量重新考虑当前可选的所有物品其实包含了抓2个甚至更多的情况！！！

5
1 2 3 4 5
1 4 3 4 1
10

20
 */
public class e背包问题byDPplus完全背包 {
	public static void main(String[] args) {
		e背包问题byDPplus完全背包 test = new e背包问题byDPplus完全背包();
		test.useDP();
	}
	
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		int[] value = new int[N];
		for (int i = 0; i < N; i++) {
			value[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		int[][] dp = new int[N][maxWeight + 1];
		int res = DP(N, weight, value, maxWeight, dp);
		System.out.println(res);
	}
	
	public int DP(int N, int[] weight, int[] value, int maxWeight, int[][] dp) {
		//第一列是volum = 0，即剩余容量=0，此列全部的元素的数值=0；因为数组初始化的时候内容都被填入0，所以这里没有额外写第一列的初始化
		for (int volume = 1; volume <= maxWeight; volume++) {//初始化第1行；从剩余容量=1开始(volume = 1，即从第2列开始)
			dp[0][volume] = value[0] * (volume / weight[0]);//(volume / weight[0])当前剩余容量能装几个A，就加上几个A的价值
		}
		for (int row = 1; row < N; row++) {//对剩下的元素填充；从第2行开始
			for (int volume = 1; volume <= maxWeight; volume++) {//从第2列开始
				if (volume >= weight[row]) {//设A的重量是weight[row]；当前剩余容量能装一个A
					int valueSelect = value[row] + dp[row][volume - weight[row]];//能装，则装一个A；把{A的价值 + “装完一个A后剩下的容量‘在优先考虑接着装A的思想下’的最优解”}尝试作为当前格子的数值
					/*
					A的价值 + “装完一个A后剩下的容量‘在优先考虑接着装A的思想下’的最优解”
					“装完一个A后剩下的容量 = volume - weight[row]
					‘在优先考虑接着装A的思想下’的 = 以volume - weight[row]这个容量为参考，接着装A(因为当前行所代表的物体数量无限，所以对于每一行，我们总是优先考虑装当前行的物体)
					最优解” = 在上面的思想下，最优解就处于当前这一行。并且位于dp[row][volum]的左侧。所以才向左找dp[row][volume - weight[row]]。
					 */
					int valueNoSelect = dp[row - 1][volume];//不管能不能装得下A；咱就是不装当前的物体A；就是把“当前剩余容量的历史最优解”尝试作为当前格子的数值
					dp[row][volume] = Math.max(valueSelect, valueNoSelect);//判断这两个尝试，谁更大；大的作为当前格子的数值
				} else {//当前剩余容量不能装一个A
					dp[row][volume] = dp[row - 1][volume];//取“当前剩余容量的历史最优解”；历史最优解永远是dp中当前列的上一行的元素
				}
			}
		}
		return dp[N - 1][maxWeight];//返回
	}
}
